<html>
<head>
  <title>LLJS : Low-Level JavaScript</title>
  <link rel="stylesheet" type="text/css" href="css/screen.css">
  <link rel="stylesheet" href="vendor/cm/lib/codemirror.css">
</head>

<body>
  <a href="https://github.com/mbebenita/LLJS"><img style="position: absolute; top: 0; right: 0; border: 0;" src="images/fork.png" alt="Fork me on GitHub"></a>
  <a href="http://mozilla.org"><img width="118" height="68" style="position: absolute; top: 0; left: 50; border: 0;" src="images/mozilla.png" alt="Mozilla"></a>
  <br>
  <div class="container">
    <h1>LLJS : Low-Level JavaScript</h1>
    <p>
      <b>LLJS</b> is a typed dialect of JavaScript that offers a C-like type system with manual memory management.
      It compiles to JavaScript and lets you write memory-efficient and GC pause-free code less painfully, in short, LLJS is the bastard child of JavaScript and C.
      LLJS is early research prototype work, so don't expect anything rock solid just yet.

      The research goal here is to explore low-level statically typed features in a high-level dynamically typed language.
      Think of it as inline assembly in C, or the <tt>unsafe</tt> keyword in C#. It's not pretty, but it gets the job done.
    </p>
    <p>
      This is an interactive tutorial, code is compiled as you type.
      To execute a piece of code press <tt>Ctrl-Enter</tt> or <tt>Cmd-Enter</tt>.
    </p>

<h2>Variables</h2>
<p>
  Unlike JavaScript, LLJS variable declarations are block scoped (only the <tt>let</tt> keyword is allowed) and can be annotated with type information.
  Untyped variable declarations are defaulted to the <tt>dyn</tt> type.
</p>

<pre class="example">
extern timer;

let x;               // Declare 'x' as dyn.
let int y;           // Declare 'y' as int.

y = (int)(x);        /* Assignment of 'x' to 'y' requires an explicit
                        cast. */

let int z = y + 1;   /* Although 'y' is of type int, the binary
                        expression y + 1 is of type num and
                        requires an implicit cast. */

let uint w = z;      /* Unsigned integer types are supported but
                        are discouraged because JavaScript engines
                        usually store numbers that are larger than
                        max signed int in doubles rather than 32-bit
                        ints. */

timer.begin("Empty For loop with signed integers.");
for (let int i = 0; i < 50000000; ++i) { }

timer.begin("Empty For loop with unsigned integers.");
for (let uint i = 0; i < 50000000; ++i) { }

timer.begin("Empty For loop with untyped integers.");
for (let i = 0; i < 50000000; ++i) { }</pre>

<h2>Data Types and Arithmetic</h2>
<p>
  LLJS has 8 numeric types: <tt>i32 (int)</tt>, <tt>u32 (uint)</tt>, <tt>i16</tt>, <tt>u16</tt>, <tt>i8</tt>,
  <tt>u8</tt>, <tt>float</tt> and <tt>double</tt> which behave as they do in C, and two additional types: <tt>num</tt> (the JavaScript number type) and <tt>dyn</tt> (any type) which are used to interoperate with the JavaScript type system.
</p>

<pre class="example">
trace("    u8: " + sizeof (u8));
trace("    i8: " + sizeof (i8));
trace("   u16: " + sizeof (u16));
trace("   i16: " + sizeof (i16));
trace("   u32: " + sizeof (u32));
trace("   i32: " + sizeof (i32));
trace(" float: " + sizeof (float));
trace("double: " + sizeof (double));

trace(" u8: " + (u8)(-1));
trace(" i8: " + (i8)(-1));
trace("u16: " + (u16)(-1));
trace("i16: " + (i16)(-1));
trace("u32: " + (u32)(-1));
trace("i32: " + (i32)(-1));

let int x = 3;
let int y = 2;

/* Arithmetic follows C semantics. Arithmetic on integers begets
   integers, truncated with | 0. */
trace("Result is an integer: " + x / y);
trace("Integral literals are typed as integers: " + 1 / 2);
trace("Floating point literals are typed as double: " + 1.1 / 2);
</pre>

<p>
  Moreover, LLJS lets you define your own struct, union and pointer types.
</p>

<pre class="example">
let int x = 42;      // Declare 'x' as int and assign 42 to it.
let int *y = &x;     /* Declare 'y' as a pointer to int and assign it
                        the address of x. Since JavaScript doesn't
                        allow taking references to variables, we
                        allocate 'x' on an emulated stack. */
let int **z = &y;    // Declare 'z' as a pointer to a pointer to int.
trace(x);
*y = 1;              // Assign to the variable pointed to by 'y'.
trace(x);
**z = 12;
trace(x);
**z = ***(&z);       // You can get as fancy as you want.
</pre>
<p>
  Structs are defined using the <tt>struct</tt> keyword.
</p>

<pre class="example">
struct Point {
  int x, y, z;
};

struct Line {
  Point start, end;
};

struct Box {
  Line left, top, right, bottom;
};

let Box b;
trace(b.top.start.x);

let Line *p = &b.top;
p->start.x = 42;
trace(b.top.start.x);</pre>

<p>
  Similarly, unions are defined using the <tt>union</tt> keyword.
</p>

<pre class="example">
union Box {
  int i;
  float f;
};

let Box box;
box.f = 123.456;
trace(box.i);        // Read back box.f as an integer.
</pre>

<h4>Functions</h4>

<p>
  Function declarations can be typed, a typed function is any function that has
  its return value or at least one of its arguments typed.
</p>

<pre class="example">

// Declare 'foo' as dyn, normal JavaScript function.
function foo() { }

// Declare 'bar' as () -> void, typed LLJS function.
function void bar() { }

// Declare 'baz' as (int, int*) -> void, typed LLJS function with typed
// arguments.
function void baz(int x, int *y) { }

// Declare 'quux' as (int, dyn, int x) -> dyn, typed LLJS function with
// mixed typed and untyped arguments.
function quux(int x, y, int z) { }

// Call 'quux'. Argument passing follows the same typechecking rules as
// assignment.
quux(-123, 2, 123.456);

// The type system is not smart enough to track types that leak into
// the dynamic type system. Safety is your responsibility.
let unsafeQuux = quux;

// Calling 'unsafeQuux' is not type-safe.
unsafeQuux("123", 2, 123.456);</pre>

<p>
  Example: you can implement a <tt>swap</tt> function in LLJS as follows:
</p>

<pre class="example">
function void swap(int *a, int *b) {
  let int t = *a;
  *a = *b;
  *b = t;
}

let int x = 1, y = 2;

swap(&x, &y);

trace("x = " + x + ", y = " + y);</pre>

<h4>Arrays</h4>

<p>
  Typed arrays can be allocated on both the heap and the stack. Stack
  allocated arrays must, as in C, be fixed length. Heap allocated
  arrays use a similar syntax to C++ dynamic arrays and their size may
  be computed at runtime.
</p>

<pre class="example">

// Stack allocated, fixed size
let int arr[100];
arr[5] = 42;
trace(arr[5]);

// Heap allocated, dynamic size
for (let int i=1; i <= 10; i++) {
  let int *heapArr = new int[i];
  arr[i-1] = i;
  trace(i + ": " + arr[i-1]);
}

// Stack allocated array inside a struct
struct ArrayStruct {
  int arr[10];
};

let ArrayStruct s;
s.arr[0] = 42;
trace(s.arr[0]);
</pre>

<h2>Objects and Memory</h2>

<p>
  LLJS has two object models: C style <tt>malloc</tt> and <tt>free</tt>, and the JavaScript object model.
  Why would you ever want to manage your memory explicitly when the JavaScript garbage collector already does the work for you.
  <!--  (LLJS offers limited support for interoperability between the two, for now at least.) -->
  Well imagine you wanted to write a linked list in JavaScript.
  You would probably chain a sequence of objects together, like so:
</p>
<pre>
 var head = {value: 0, next: null}, tail = head;

 function add(value) {
   var next = {value: value, next: null};
   tail.next = next;
   tail = next;
 }
</pre>
<p>
  This is inefficient for several reasons. Objects in JavaScript are not cheap, they need to carry around lots of extra information and can be
  many times larger than their C style counterparts, moreover property access can be slow.
  Chaining several property accesses together <tt>x.y.z.w</tt> usually results in several memory indirections, in LLJS this compiles into a single memory access with a computed offset.
  <br>
  Usually, when you use a garbage collector you can design a very fast bump allocator which is probably more efficient than LLJS's <tt>malloc</tt>, but nothing is free, you pay for it later during
  garbage collection. If you have explicit control over memory, you can always do better (if you put in the effort).

  In LLJS you can write a much more space efficient linked list using pointers and structs.
  <!-- With great power comes great responsibility, so what is malloc'ed must be freed, even in JavaScript. -->
</p>

<pre class="example">
struct Node {
  Node *next;
  int value;
};

let Node *head = new Node, *tail = head;

function Node *add(int value) {
  let Node *next = new Node;
  next->value = value;
  tail->next = next;
  tail = next;
  return next;
}

trace(add(1));
trace(add(2));
trace(add(3));

traceList(head->next);

function void traceList(Node *p) {
  while (p) {
    trace("Node at address: " + p + ", has value: " + p->value);
    p = p->next;
  }
}</pre>

<p>
  You may notice that the <tt>new</tt> operator behaves differently whenever it's applied to a type name. It computes the size of
  the data item in bytes, and calls <tt>malloc</tt>.
</p>

<pre class="example">
// Import malloc. The casting is annoying -- we don't have a good
// story for typed imports yet.
typedef byte *malloc_ty(uint);
let malloc_ty malloc = (malloc_ty)(require('memory').malloc);

// Allocate an int on the heap using new.
let int *y = malloc(sizeof(int));
trace(y);

// Alternate, more convenient syntax.
let int *x = new int;
trace(x);</pre>

<h3>Memory</h3>
<p>
LLJS manages memory using <a href="https://developer.mozilla.org/en/JavaScript_typed_arrays">Typed Arrays</a>. It allocates one large <tt>ArrayBuffer</tt> ahead of time,
and creates several typed array views on this buffer, one for each of the primitive data types.
For instance: <tt>U4</tt>, <tt>U2</tt> and <tt>U1</tt> for <tt>u32</tt>, <tt>u16</tt> and <tt>u8</tt> respectively (see figure below).
(For a more in-depth discussion, see how <a href="https://github.com/kripken/emscripten/wiki/Code-Generation-Modes">Emscripten</a> does it.)
This really is the same thing as the scaled/indexed addressing mode in x86.
The only drawback is that you can't read unaligned data, but this is actually a good thing, since unaligned access is usually slower, or not even possible on some platforms.

<img src="images/arrays.png" style="display: block;   margin-left: auto;   margin-right: auto;">
</p>
<h3>Pointers</h3>
<p>
  Since our managed memory is actually addressable at byte and integer levels, there is no reason to store pointers as byte addresses. Instead we store them as indices, implicitly scaled by their own base type.
  For example, the pointer dereference <tt>*p</tt>, where <tt>p</tt> is of type <tt>int*</tt>, gets compiled into <tt>U4[p]</tt>.
  Had we stored pointers as byte addresses, we would have compiled it to <tt>U32[p >> 2]</tt>.
  This eliminates address computations at each memory access, but requires that we perform pointer conversions whenever we cast from one pointer type to another, see below:
</p>

<pre class="example">
let int *x = (byte *)(8);
let u16 *y = x;
let int z = *x + *y;</pre>

<h3>Malloc & Free</h3>
<p>
  The LLJS memory allocator, transcribed from the K&R C implementation, is itself implemented in LLJS. For now, we allocate one large chunk of memory 32 MB and let
  <tt>malloc</tt> and <tt>free</tt> manage it. We reserve the first two words in memory for the Heap Pointer <tt>HP</tt> that points to the latest allocated page by <tt>sbrk</tt>
  and the Stack Pointer <tt>SP</tt> which always points to the top of the stack. The heap grows downward (towards higher addresses) and the stack grows upward.
  For now, when the two meet we run out of memory, but we could resize the array buffer copy the heap over and resume.
  <img src="images/heap.png" style="display: block;   margin-left: auto;   margin-right: auto;">
</p>

<h3>Contrived Allocation Benchmark</h3>

<p>Here is a contrived allocation benchmark that compares allocating linked
list nodes with the slow K&R malloc versus using native JavaScript objects. We
allocate and free 250,000 structs of 40 bytes each and compare it against
allocating 250,000 objects with 4 extra properties. The struct version is much
more space efficient, and as we will see, performs at least as well, if
not better, than allocating objects.</p>

<p>At the time of this writing, allocating structs is about as fast as
allocating objects on v8, but noticeably faster on SpiderMonkey.</p>

<pre class="example">
struct Node {
  Node *next;
  int val;
  double pad1, pad2, pad3, pad4;
};

function ObjNode() {
  this.next = null;
  this.val = 0;
  this.pad1 = this.pad2 = this.pad3 = this.pad4 = 0;
}

extern Date;

const int n = 250000;

function benchStruct() {
  let start = new Date();
  let Node *head;
  for (let int i = 0; i < n; ++i) {
    let Node *prev = head;
    head = new Node;
    head->next = prev;
    head->val = i;
  }

  let double sum = 0;
  for (let int i = 0; i < n; ++i) {
    let Node *prev = head;
    sum += head->val;
    head = head->next;
    delete prev;
  }

  return new Date() - start;
}

function benchObject() {
  let start = new Date();
  let head;
  for (let i = 0; i < n; ++i) {
    let prev = head;
    head = new ObjNode();
    head.next = prev;
    head.val = i;
  }

  let sum = 0;
  for (let i = 0; i < n; ++i) {
    sum += head.val;
    head = head.next;
  }

  return new Date() - start;
}

// Warm up the JIT.
benchStruct(); benchStruct();
benchObject(); benchObject();

let dt;

dt = 0;
for (let i = 0; i < 10; ++i) {
  dt += benchStruct();
}
trace("Structs: " + dt / 10 + " ms");

dt = 0;
for (let i = 0; i < 10; ++i) {
  dt += benchObject();
}
trace("Objects: " + dt / 10 + " ms");
</pre>

<h4>Acknowledgements</h4>
<p>
  <a href="https://github.com/kripken/emscripten">Emscripten</a> for the inspiration,
  <a href="http://esprima.org/">Esprima</a> and
  <a href="https://github.com/Constellation/escodegen">Escodegen</a> for parsing and code generation, and
  <a href="http://codemirror.net/">CodeMirror</a> for the code editor.
</p>
</div>

<script src="vendor/cm/lib/codemirror.js"></script>
<script src="vendor/cm/mode/javascript/javascript.js"></script>
<script src="vendor/jquery-1.7.2.min.js"></script>

<script src="lljs/estransform.js"></script>
<script src="lljs/types.js"></script>
<script src="lljs/util.js"></script>
<script src="lljs/scope.js"></script>
<script src="lljs/esprima.js"></script>
<script src="lljs/escodegen.js"></script>
<script src="lljs/compiler.js"></script>
<script src="lljs/memcheck.js"></script>
<script src="lljs/memory.js"></script>
<script src="lljs/ljc.js"></script>

<script>
var id = 0;
$('.example').replaceWith(function() {
  var src = this.innerHTML;
  var lineCount = src.split("\n").length;
  var res = '<table class="example"><tr><td><textarea id="ex:' + id + ':source" class="jcCode" rows="' + lineCount + '" spellcheck="false">' + src + '</textarea></td><td valign="top"><pre id="ex:' + id + ':result" class="jcResult"></pre></td></tr></table><table class="toolbar"><tr><td><div id="ex:' + id + '" class="minibutton run" title="Ctrl-Enter">Run</div><!--<div id="ex:' + id + '" style="margin-left: 10px" class="minibutton runMemCheck" title="Ctrl-Enter">Run with MemCheck</div>--></td></tr></table>';
  id ++;
  return res;
});

var lastMarker;

function compileExample(ex) {
  if (lastMarker) {
    this.clearMarker(lastMarker);
  }
  var number = ex.split(":")[1];
  var result = document.getElementById("ex:" + number + ":result");
  try {
    var name;
    if (Number(number) === id - 1) {
      name = "memory";
    } else {
      name = "ex" + number;
    }
    var source = this.getValue();
    source = 'extern trace;\n' + source;
    result.innerHTML = LJC.compile(source, { bare: true, memcheck: false, filename: name });
  } catch (x) {
    result.innerHTML = x.message;
    if (x.lineNumber) {
      lastMarker = this.setMarker(x.lineNumber - 1, "<span style=\"color: #900\">x</span> %N%");
    }
  }
}

var Timer = (function () {
  function timer() {
    this.name = null;
    this.start = null;
  }

  timer.prototype.begin = function (name) {
    if (this.start) {
      if (this.name) {
        trace("Timer: " + (new Date() - this.start) + " ms: " + this.name);
      } else {
        trace("Timer: " + (new Date() - this.start) + " ms.");
      }
    }
    this.start = new Date();
    this.name = name;
  };

  return timer;
})();

var timer;
var trace;

function require(name) {
  if (name === "memory") {
    return memory;
  }
  return null;
}

function executeExample(id, enableMemCheck) {
  var number = id.split(":")[1];
  var result = document.getElementById("ex:" + number + ":result");
  try {
    if (enableMemCheck) {
      memory.set_memcheck(true);
    } else {
      memory.reset();
    }

    timer = new Timer();

    result.innerHTML = "";

    trace = function (x) {
      result.innerHTML += x + "\n";
    };

    start = new Date();
    var source = this.getValue();
    if (enableMemCheck) {
      source = 'extern trace;\nlet $$$M = require("memory");\n' +
               source + '\ntrace($$$M.memcheck.report());';
    } else {
      source = 'extern trace;\n' + source;
    }
    var code = LJC.compile(source, { memcheck: !!enableMemCheck, filename: "ex" + number});
    result.innerHTML += "Compiled in: " + (new Date() - start) + " ms\n";
    result.innerHTML += "-----------------------------------------------------\n";

    start = new Date();
    new Function(code)();

    timer.begin(null);
    result.innerHTML += "-----------------------------------------------------\n";
    result.innerHTML += "Executed in : " + (new Date() - start) + " ms.";

  } catch (x) {
    result.innerHTML = x.message;
  }
}

var codeMirrors = {};

$('.jcCode').each(function() {
  var id = this.id;
  var cm = codeMirrors[id] = CodeMirror.fromTextArea(this, {
    tabSize: 2,
    lineNumbers: true,
    gutter: true,
    onChange: function () {
      compileExample.call(cm, id);
    },
    extraKeys: {
      "Ctrl-Enter": function () {
        executeExample.call(cm, id);
      },
      "Cmd-Enter": function () {
        executeExample.call(cm, id);
      }
    }
  });
  compileExample.call(cm, id);
});

$('.run').click(function() {
  var number = this.id.split(":")[1];
  executeExample.call(codeMirrors["ex:" + number + ":source"], this.id);
});

$('.runMemCheck').click(function() {
  var number = this.id.split(":")[1];
  executeExample.call(codeMirrors["ex:" + number + ":source"], this.id, true);
});

</script>
</body>
</html>
